// Created by WXX on 2021/11/29 21:48
#include "MyTree.h"

using namespace std;

/**
 * 执行用时：4 ms, 在所有 C++ 提交中击败了83.69%的用户
 * 内存消耗：9.7 MB, 在所有 C++ 提交中击败了38.63%的用户
 */
class Solution {
public:
    int maxAncestorDiff(TreeNode* root) {
        int val = root->val;
        return max(dfs(root->left, val, val), dfs(root->right, val, val));
    }

    int dfs(TreeNode* root, int minv, int maxv) {

        if (!root) return -1;
        int val = root->val;
        int res = max(abs(val - minv), abs(val - maxv));
        minv = min(minv, val);
        maxv = max(maxv, val);
        res = max(res, dfs(root->left, minv, maxv));
        res = max(res, dfs(root->right, minv, maxv));
        return res;
    }
};

int main() {

    int nu = INT_MAX;
    vector<int> nums = {
            8,
            3, 10,
            1, 6, nu, 14,
            nu, nu, 4, 7, nu, nu, 13, nu
    };
    TreeNode *root = MyTree(nums).getRoot();
    cout << Solution().maxAncestorDiff(root) << endl;  // 7

    return 0;
}
